package com.shm.leetcode;

import java.util.Arrays;

/**
 * @author SHM
 */
public class MinDaysSpiltIslands {

    /**
     * 结果只可能有三种：
     *
     * 岛屿数为0，即全是水。结果是0。
     * 岛屿数大于1。不需要分离，结果也是0。
     * 岛屿数为1，这时候，就要尝试将岛屿分成两个了。
     * 分两种情况：
     * 只需要一次分离，即把一个岛屿置为0，就可以分成两个岛屿。
     * 最差的情况，比如整个矩阵都1的时候。这个时候，肯定是选右上、右下、左上、左下四个角中的其中之一，将它分离成一个单独的岛屿。比如，选左下角，只要把它的上方、左方的岛屿置为0即可，所以我们最多需要两次操作。
     * 如何获取连通的岛屿数？
     * dfs
     *
     * 如何分离岛屿？
     * 其实很简单。
     *
     * 遍历整个矩阵，一个个尝试，把岛屿置为0，然后重新对矩阵进行union，获取连通的岛屿数。
     * 如果这时候，岛屿数大于1。说明只要一次操作，我们就可以进行分离，直接return 1即可。
     * 否则，恢复岛屿，即重置为1。重复步骤1。
     * 遍历完整个矩阵，没有发现只改变一个岛屿，就能进行分离的情况。那只能进行两次操作了。
     *
     * 作者：TuFeiBaBa
     * 链接：https://leetcode-cn.com/problems/minimum-number-of-days-to-disconnect-island/solution/bing-cha-ji-jie-guo-zhi-ke-neng-shi-0-1-2-by-tufei/
     */

    int N = 30;
    boolean[][] visited = new boolean[N][N];
    int n,m;
    int[][] direction = {{1,0},{0,1},{-1,0},{0,-1}};
    public int minDays(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        if (check(grid)){
            return 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]==1){
                    grid[i][j]=0;
                    if (check(grid)){
                        return 1;
                    }
                    //恢复矩阵
                    grid[i][j]=1;
                }
            }
        }
        return 2;
    }

    public boolean check(int[][] grid){
        //重置visited
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i],false);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j]==1){
                    dfs(grid,i,j);
                    count++;
                }
            }
        }
        return count == 0 || count > 1;
    }

    public void dfs(int[][] grid,int x,int y){
        if (visited[x][y]){
            return;
        }
        visited[x][y] = true;
        for (int[] d : direction) {
            int dx = x+d[0],dy=y+d[1];
            if (dx>=0&&dx<n&&dy>=0&&dy<m&&!visited[dx][dy]&&grid[dx][dy]==1){
                dfs(grid,dx,dy);
            }
        }
    }
}
